This disclosure is related to digital circuits for data processing, and more specifically, to digital adders.
A digital adder circuit digitally adds two digital numbers. Adding is a basic data manipulation in digital processing. Many electronic data processing devices, including microprocessors, implement one or more digital adders.
Binary adders are widely used in various digital electronic devices. Adding two binary numbers includes adding bits at each bit position of two input binary numbers using an exclusive or (xe2x80x9cXORxe2x80x9d) operation, and also adding the corresponding carry-in bit from an adjacent lesser significant bit position, to produce a sum bit for that bit-position. A carry-out bit produced by that sum is determined and is then sent to the next, more significant bit position.
The carry-out bit from each bit position is zero, i.e., a xe2x80x9ckillxe2x80x9d, when two inputs to be added are both zero, no matter what the carry-in bit is. When two inputs to the bit position are both one, the carry-out bit is always one, i.e., a xe2x80x9cgeneratexe2x80x9d. The value of the carry-in bit does not affect the carry-out bit. However, when the two inputs are different, the carry-out bit is the carry-in bit to that bit position, i.e., the bit position xe2x80x9cpropagatesxe2x80x9d its carry-in bit to the next bit position. Binary adders use a special logic, a xe2x80x9cPGK cellxe2x80x9d, to process the carry at each bit position. Each PGK cell includes logic elements such as transistors to perform the above carry processing based on whether the addition operation at the bit position produces a propagate (xe2x80x9cPxe2x80x9d), a generate (xe2x80x9cGxe2x80x9d), or a kill (xe2x80x9cKxe2x80x9d).
This carry computation by each PGK cell takes time and need be carried out at each bit position. Hence, the carry computation can significantly affect the overall processing speed of a binary adder, especially, when the bit number is large, such as in a 32-bit adder. It is therefore desirable to develop binary adders that can efficiently process the carry information at a high speed.
The present devices and techniques include mechanisms that allow propagation of a carry bit by skipping or bypassing two or more selected bit positions in binary adders, whenever permissible, though two or more levels of carry-skip paths in the carry processing part of the adders.
One embodiment of such adders includes carry-processing cells connected in series, carry-skip cells each coupled across a group of carry-processing cells, and a plurality of logic gates to control the carry-skip cells.
Each carry-processing cells processes carry information to generate a carry signal. Each carry-skip cell is coupled across a respective group of carry-processing cells to send a carry directly to a carry-processing cell that is subsequent to a most significant bit position in the respective group, when each and every carry-processing cell in the respective group produces a propagate.
Each logic gate is coupled between a carry-skip cell and a respective group of carry-processing cells to receive all carry signals from the respective group to produce an output. The number of carry-processing cells in all groups of carry-processing cells associated with the carry-skip cells is less than a maximum number. This number has a relationship with a total number of the carry-processing cells in the adder.